#include "AI5.h"

// Max and Min macros
#ifndef max
	#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
#endif

#ifndef min
	#define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
#endif


/*takes wins as a n by 4 2D array and looks at the different wins and evaluates which player won
 and their point values
 
 This function has to do 3 things:
 1) figure out which player won - return positive or negative values
 2) Figure out what point value they won with - arrangment of the peices
 3) If two players have the same winning value - return 1 point
 */
int evalWin(char wins[150][4])
{
   
    int i = 0;
    int points = 0;
    int bestwin = 0;
    int worstwin = 0;
    int redpoints = 0;
    int bluepoints = 0;
    do{
        //fprintf(f, f, "checking case %s\n", wins[i]);
        //check for tie - if there is nothing in the wins array
        if(wins[0][0] == '\0' || wins[0][0] == 0)
        {
            //fprintf(f, "0");//no wins in array - no nothing in array
            points = 0;
            return 0;
        }
        else//we have at least one win - check it out
        {
            //first - check for the good wins - where the first two char's will match
            if(wins[i][0] == wins[i][1])//same colour first two pieces
            {
               
                if(wins[i][0] == 'r')
                {
                    redpoints += 5;
                    points = -5;
                }//we won
                else if(wins[i][0] == 'b')
                {
                    bluepoints += 5;
                    points = 5;
                }
               
                else if(wins[i][0] == 'g')//don't know who won yet
                {
                    if(wins[i][2] == 'r')
                    {
                        redpoints += 5;
                        points = -5;
                    }//we won
                    else
                    {
                        bluepoints += 5;
                        points = 5;
                    }
                }
            }
           
            else if(wins[i][1] == wins[i][2])//middle two are same colour - 4 points
            {
               
                if(wins[i][0] == 'r')
                {
                    redpoints += 4;
                    points = -4;
                }//we won
                else if(wins[i][0] == 'b')
                {
                    bluepoints += 4;
                    points = 4;
                }
                else//first piece is green
                {//check the second piece
                    if(wins[i][1] == 'r')
                    {
                        redpoints += 4;
                        points = -4;
                    }//we won   
                    else if(wins[i][1] == 'b')
                    {
                        bluepoints += 4;
                        points = 4;
                    }
                   
                }
               
            }
            else //3 points will be awarded
            {
                if(wins[i][0] == 'r')
                {
                    redpoints += 3;
                    points = -3;
                }//we won
                else if(wins[i][0] == 'b')
                {
                    bluepoints += 3;
                    points = 3;
                }
                else//first piece is green
                {//check the second piece
                    if(wins[i][1] == 'r')
                    {
                        redpoints += 3;
                        points = -3;
                    }//we won
                    else if(wins[i][1] == 'b') 
                    {
                        bluepoints += 3;
                        points = 3;
                    }
                }
            }
           
           
           
        }
        if(points > 0)
        {
            if(bestwin < points)
                bestwin = points;
        }
        else
            if(worstwin > points)
                worstwin = points;
       
        i++;
    }while(wins[i][0] != 0);
   
   
    if( redpoints - bluepoints > 0)
        points = worstwin;
    else if(redpoints - bluepoints == 0)
        points = 1;
    else
        points = bestwin;
   
    //fprintf(f,  "%d\n", points);
    return points;
}

/*
*	Reads from stdin to populate the board object 
*/
int readBoard(char board[columns+2][rows+2])
{
    int i, j, p = 0;
   
    // Populate board array
    for (i = 0; i < columns+2; i++)
    {
        // Padding columns on left and right sides of board
        if (i == 0 || i == columns+1)
        {
            for(j = 0; j < rows+2; j++)
                board[i][j] = SPACE;
            continue;
        }
        // Padding Row over bottom of board
        board[i][0] = SPACE;
        for (j = 1; j < rows+1; j++)
        {
            scanf(",%c", &board[i][j]);
            if(board[i][j] < 's')
                p++;
        }
        // Padding row over top of board
        board[i][j] = SPACE;
    }
    return p;
}

/*
*	Looks at the current state of the board and returns a list of all "wins" found. Only checks vectors involving the last_played piece,
*	because if a win existed before the piece was played, it would have been found in an earlier call to findWins().
*/
void findWins(char board[columns+2][rows+2], char wins[150][4], int last_played)
{
    // last_piece_x and last_piece_y hold co-ordinates of the last played piece, that is the piece that must be checked for wins
    int last_piece_x = last_played, last_piece_y, winIndex = 0;
    int i;
    // get the last piece's Y co-ordinate
    for (i=1;i<rows+1;i++)
    {
        if(board[last_piece_x][i] == SPACE)
            break;
        last_piece_y = i;
    }
   
    //fprintf(f, "Last Moved Piece's co-ordinates:%i, %i, %c\n", last_piece_x, last_piece_y, board[last_piece_x][last_piece_y]);   
   
    /*
     * How this works is: For each directional axis (X, Y, Diagonal Down Left-to-Right, and Diagonal Up Left-to-Right), the last dropped
     * piece can be in 4 vectors (it can be in positions 0-3). For each of these possible positions, the algorithm grabs the 4 pieces
     * and then checks that vector to see if it is a win. If so, it adds it to the wins array.
     */
   
    // Diagonal Top Left<->Bottom Right
    //fprintf(f, "Beginning Diagonal Loop\n");
    for(i=0;i<4;i++) // Check each of the 4 possible positions for the last dropped piece
    {
        short int offset, size = 1;
       
        //fprintf(f, "for position:%i\n", i);
       
        // The co-ordinates used to build the vector to check on. Note these move diagonally to the right,down.
        short int start_piece_x = last_piece_x + i, start_piece_y = last_piece_y - i;
        //fprintf(f, "start_piece co-ordinates are: %i, %i\n", start_piece_x, start_piece_y);
        // If the starting piece is a space, stop moving in that direction
        if (board[start_piece_x][start_piece_y] == SPACE)
        {
            //fprintf(f, "BREAK1: Found Space, finished looking at diagonal!\n", i);
            break;
        }
       
        char win[4] = {board[start_piece_x][start_piece_y],'s','s','s'};
        // Build a vector going diagonally to the up, left
        for (offset = 1;offset < 4;offset++)
        {
            if (board[start_piece_x-offset][start_piece_y+offset] == SPACE)
            {
                //fprintf(f, "BREAK2: Found Space While building a vector\n");
                break;
            }   
            win[size++] = board[start_piece_x-offset][start_piece_y+offset];
        }
        if (size == 4) // Found a four piece vector (No Spaces)
        {
            //fprintf(f, "Successfully Found a Four-Piece Vector: %s\n", win);
            int k;
            for (k=0;k<12;k++)
            {
                if (strncmp(win,WINS_LOOKUP[k], 4) == 0)
                {
                    //fprintf(f, "Found a Win! Vector is %s\n", win);
                    strcpy(wins[winIndex++], win);
                }
            }
           
        }
    }
    // Top<->Bottom
    //fprintf(f, "Beginning Vertical Loop\n");
    for(i=0;i<4;i++)
    {
        short int offset, size = 1;
        //fprintf(f, "for position:%i\n", i);
        short int start_piece_x = last_piece_x, start_piece_y = last_piece_y - i;
        //fprintf(f, "start_piece co-ordinates are: %i, %i\n", start_piece_x, start_piece_y);
        if (board[start_piece_x][start_piece_y] == SPACE)
        {
            //fprintf(f, "BREAK1: Found Space, finished looking at Vertical!\n", i);
            break;
        }
       
        char win[4] = {board[start_piece_x][start_piece_y],'s','s','s'};
        // Build a vector going diagonally to the up, left
        for (offset = 1;offset < 4;offset++)
        {
            if (board[start_piece_x][start_piece_y+offset] == SPACE)
            {
                //fprintf(f, "BREAK2: Found Space While building a vector\n");
                break;
            }
            win[size++] = board[start_piece_x][start_piece_y+offset];
        }
        if (size == 4) // Found a four piece vector (No Spaces)
        {
            //fprintf(f, "Successfully Found a Four-Piece Vector: %s\n", win);
            int k;
            for (k=0;k<12;k++)
            {
                if (strncmp(win,WINS_LOOKUP[k], 4) == 0)
                {
                    //fprintf(f, "Found a Win! Vector is %s\n", win);
                    strcpy(wins[winIndex++], win);
                }
            }
           
        }
    }
    // Diagonal Bottom Left<->Top Right
    //fprintf(f, "Beginning 2nd Diagonal Loop\n");
    for(i=0;i<4;i++)
    {
        short int offset, size = 1;
        //fprintf(f, "for position:%i\n", i);
       
        short int start_piece_x = last_piece_x - i, start_piece_y = last_piece_y - i;
        //fprintf(f, "start_piece co-ordinates are: %i, %i\n", start_piece_x, start_piece_y);
        if (board[start_piece_x][start_piece_y] == SPACE)
        {
            //fprintf(f, "BREAK1: Found Space, finished looking at 2nd diagonal!\n", i);
            break;
        }
       
        char win[4] = {board[start_piece_x][start_piece_y],'s','s','s'};
        // Build a vector going diagonally to the up, left
        for (offset = 1;offset < 4;offset++)
        {
            if (board[start_piece_x+offset][start_piece_y+offset] == SPACE)
            {
                //fprintf(f, "BREAK2: Found Space While building a vector\n");
                break;
            }
           
            win[size++] = board[start_piece_x+offset][start_piece_y+offset];
        }
        if (size == 4) // Found a four piece vector (No Spaces)
        {
            //fprintf(f, "Successfully Found a Four-Piece Vector: %s\n", win);
            int k;
            for (k=0;k<12;k++)
            {
                if (strncmp(win,WINS_LOOKUP[k], 4) == 0)
                {
                    //fprintf(f, "Found a Win! Vector is %s\n", win);
                    strcpy(wins[winIndex++], win);
                }
            }
           
        }
    }
    //  Left<->Right
    //fprintf(f, "Beginning Horizontal Loop\n");
    for(i=0;i<4;i++)
    {
        short int offset, size = 1;
        //fprintf(f, "for position:%i\n", i);
       
        short int start_piece_x = last_piece_x - i, start_piece_y = last_piece_y;
        //fprintf(f, "start_piece co-ordinates are: %i, %i\n", start_piece_x, start_piece_y);
        if (board[start_piece_x][start_piece_y] == SPACE)
        {
            //fprintf(f, "BREAK1: Found Space, finished looking at Horizontal!\n", i);
            break;
        }
       
        char win[4] = {board[start_piece_x][start_piece_y],'s','s','s'};
        // Build a vector going diagonally to the up, left
        for (offset = 1;offset < 4;offset++)
        {
            if (board[start_piece_x+offset][start_piece_y] == SPACE)
            {
                //fprintf(f, "BREAK2: Found Space While building a vector\n");
                break;
            }
           
            win[size++] = board[start_piece_x+offset][start_piece_y];
        }
        if (size == 4) // Found a four piece vector (No Spaces)
        {
            //fprintf(f, "Successfully Found a Four-Piece Vector: %s\n", win);
            int k;
            for (k=0;k<12;k++)
            {
                if (strncmp(win,WINS_LOOKUP[k], 4) == 0)
                {
                    //fprintf(f, "Found a Win! Vector is %s\n", win);
                    strcpy(wins[winIndex++], win);
                }
            }
           
        }
    }
    // End with "end of wins" flag vector, to signal the end of wins
    wins[winIndex][0] = END_OF_WINS;
}

/* 
*	Print Board function for debugging. Prints the current board object in the following format:
*	Bottom->Top
*	Bottom->Top
*	.
*	.
*	.
*	Bottom->Top
*/
void printBoard(char board[columns+2][rows+2])
{
    int i, j;

    for (i = 0; i < rows+2; i++)
    {
        fprintf(f, "\t");
        for (j = 0; j < columns+2; j++)
        {
            fprintf(f, "%c ", board[j][i]);
        }
        fprintf(f, "\n");
    }
    fprintf(f, "\n");
}

/*
*	Main function for checking wins on a board. Finds wins, then evaluates a final score based on these win vectors.
*/
int isWin(char board[columns+2][rows+2], int last_played)
{
    char wins[150][4];

    findWins(board, wins, last_played);
    return evalWin(wins);
   
}

/*
*	
*/
int tryMove(char board[columns+2][rows+2], int col, char piece)
{
    int i, row = -1, depth = 3;
    // First, see if column has room for another piece
    printBoard(board);
    for(i=1;i<=rows;i++)
    {
        if(board[col][i] == SPACE)
        {
            row = i;
            break;               
        }                 
    }
    if (row == -1)
    {
    	    /* THIS ISNT WORKING*******************************************************/
        return -9999999;//really big number so we don't play in this col       
    }
    else
    {
        board[col][row] = piece;
        //rank the moves by the number of points we can get to
        int score = 10000*isWin(board, col) + lookAhead(board, depth-1);
        board[col][row] = SPACE;
        return score;
    }
}


//Implements Minimax search - lowest level returns the min, then the upper levels take the
//max value of the returned mins

int lookAhead(char board[columns+2][rows+2], int depth)
{
    int  i, j, tmp = 0, max_move = -1, min_move = -1, max = 0, min = 0, row = 0;
    char piece;

   
    //printBoard(board);
    //return the best min value
    if(depth == 0)
    {
        // Loop through all possible moves
        for(i=1;i<=columns;i++)
        {
            // Find the row the piece will fall to
            //Don't use tryMove so we can recurse...
            for(j=1;j<=rows;j++)
            {
                if(board[i][j] == SPACE)
                {
                    row = j;
                    break;               
                }                 
            }
        }
       
       
        for(i=1;i<=columns;i++)
        {
            // Find the row the piece will fall to
            //Don't use tryMove so we can recurse...
            for(j=1;j<=rows;j++)
            {
                if(board[i][j] == SPACE)
                {
                    row = j;
                    break;               
                }                 
            }
           
            board[i][row] = BLUE;
            tmp = isWin(board, i);
            if(tmp < 0 && tmp > min)
            {
                min = tmp;
            //    min_move = i;
            }
            //tmp += isWin(board, i) + lookAhead(board, depth-1);
#if DEBUG
            fprintf(f, "tmp: %d\n", tmp);
#endif
           
            // Try placing a Green piece  
            board[i][row] = GREEN;
            tmp = isWin(board, i);
            if(tmp < 0 && tmp > min)
            {
                min = tmp;
            //    min_move = i;
            }
            //tmp += isWin(board, i) + lookAhead(board, depth-1);
#if DEBUG
            fprintf(f, "tmp: %d\n", tmp);
#endif
            // Simulate the opponent placing Red here
            board[i][row] = RED;
            tmp = isWin(board, i);
            if(tmp < 0 && tmp > min)
            {
                min = tmp;
            //    min_move = i;
            }
            //tmp += isWin(board, i) + lookAhead(board, depth-1);
#if DEBUG
            fprintf(f, "tmp: %d\n", tmp);
#endif

            board[i][row] = SPACE;//reset the board
           
        }
        return min;
    }
   
        /*
         Here we return the col with the max value
         */
    // Loop through all possible moves
    for(i=1;i<=columns;i++)
    {
        // Find the row the piece will fall to
        //Don't use tryMove so we can recurse...
        for(j=1;j<=rows;j++)
        {
            if(board[i][j] == SPACE)
            {
                row = j;
                break;               
            }                 
        }
       
        board[i][row] = BLUE;
        tmp += (isWin(board, i)*10000) + lookAhead(board, depth-1);
        if(max < tmp)
        {
            max = tmp;
        }
        //tmp += isWin(board, i) + lookAhead(board, depth-1);
#if DEBUG
        fprintf(f, "tmp: %d\n", tmp);
#endif
       
        // Try placing a Green piece  
        board[i][row] = GREEN;
        tmp += (isWin(board, i)*10000) + lookAhead(board, depth-1);
        if(max < tmp)
        {
            max = tmp;
        }
        //tmp += isWin(board, i) + lookAhead(board, depth-1);
#if DEBUG
        fprintf(f, "tmp: %d\n", tmp);
#endif
        // Simulate the opponent placing Red here
        board[i][row] = RED;
        tmp += (isWin(board, i)*10000) + lookAhead(board, depth-1);
        if(max < tmp)
        {
            max = tmp;
        }
        //tmp += isWin(board, i) + lookAhead(board, depth-1);
#if DEBUG
        fprintf(f, "tmp: %d\n", tmp);
#endif

        board[i][row] = SPACE;//reset the board
       
    }
   
    //Sort the buffer and explore children
   
   
    //fprintf(f, "LookAhead %d - max: %d, min: %d\n", depth, max, min);
    /*
     if(max > 0) // There's a Win
     return max;
     else if(min < 0) // There's a Opponent's Win to Block
     return min;
     else
     */
    return max;
   
   
   
   
}

int makeMove(char board[columns+2][rows+2])
{
    int  i,tmp, max_move = -1, min_move = -1, max = 0, min = 0;
    char piece;
    // Loop through all possible moves
    for(i=1;i<=columns;i++)
    {
       
        // Try placing a Blue piece
        tmp = tryMove(board, i, BLUE);
#if DEBUG
        fprintf(f, "Trying col: %d - Piece: Blue - SCORE: %d\n\n", i, tmp);
#endif
        if (tmp > max)
        {
            max_move = i;
            piece = BLUE;
            max = tmp;                 
        }
        // Try placing a Green piece  
        tmp = tryMove(board, i, GREEN);
#if DEBUG
        fprintf(f, "Trying col: %d - Piece: Green - SCORE: %d\n\n", i, tmp);
#endif
        if (tmp > max)
        {
            max_move = i;
            piece = GREEN;
            max = tmp;                 
        }
        else if (tmp < min)
        {
            min_move = i;
            min = tmp;                 
        }
        // Simulate the opponent placing Red here
        tmp = tryMove(board, i, RED);
        fprintf(f, "Trying col: %d - Piece: Red - SCORE: %d\n\n", i, tmp);
        if (tmp < min)
        {
            min_move = i;
            min = tmp;                 
        }                   
    }
    /*if(min < 0) // There's a Opponent's Win to Block
     fprintf(f, "(%d, %c)", min_move, BLUE);
     
     else
     */if(max > 0) // There's a Win
         printf("(%d, %c)", max_move, piece);
    if(min < 0)
        printf("(%d, b)", min_move, piece);

   
   
}


/*
*	Controller function for calling recursive Minimax, then making the optimal move found by that function.
*/
int chooseMove(char board[columns+2][rows+2])
{
	
	int i, j;
	int playerBlue = 1; // 1 for Blue (Max) Player, 0 for Red (Min) player

	int bestScore = 0, bestColumn = -1;		// Best move found so far
	char bestPiece = 's';
	int score = 0;

	// Look at the possible moves for this turn and find any immediate wins
	for (i=1;i<=columns;i++)
	{

		// 1: Check if column is full; if so, skip it.
		int nextSpace = -1;
		for (j=0;j<=rows;j++)
		{
			if(board[i][j] == 's')
			{
				nextSpace = j;
				break;
			}
		}
		if(nextSpace == -1)
			continue;

		// 2: Check for immediate wins
		board[i][nextSpace] = 'b';
		if ((score = isWin(board, i)) > 0)
		{
			// Found a Win with a Blue Piece
			if (score > bestScore)
			{
				bestScore = score;
				bestColumn = i;
				bestPiece = 'b';
			}
		}
		board[i][nextSpace] = 'g';
		if ((score = isWin(board, i)) > 0)
		{
			// Found a Win with a Green Piece
			if (score > bestScore)
			{
				bestScore = score;
				bestColumn = i;
				bestPiece = 'g';
			}
		}
		board[i][nextSpace] = 's'; // Remove hypothetical piece
	}

	// If an immediate win was found, make that move
	// TODO: If combining into one function, make this happen at top level only, for obvious reasons.
	if (bestScore > 0)
	{
		printf("(%d, %c)", bestColumn, bestPiece);
		return 0;
	}

	// TODO: implement MAXINT and -MAXINT
	score = 0;
	// 2: Call Recursive Minimax to determine best move to make
	for (i=1;i<=columns;i++)
	{

		// 2a: Check if column is full; if so, skip it.
		int nextSpace = -1;
		for (j=0;j<=rows;j++)
		{
			if(board[i][j] == 's')
			{
				nextSpace = j;
				break;
			}
		}
		if(nextSpace == -1)
			continue;

		// 2b: Call Minimax 
		// TODO
		//int result = (-1)*minimax(
	}


	return 0;
}

int minimax(char board[columns+2][rows+2], int depth, int myColour)
{
	// TODO: Combine with above?

	return 0;
}

int main( int argc, char **argv)
{
	// First build board object
	scanf("(%d,%d,%d,%d,%d,%d", &columns, &rows, &last_move, &total_time, &player_1_time, &last_move_time);
	char board[columns+2][rows+2];
    readBoard(board);

	// Make Move
	chooseMove(board);

	return 0;
  
}


